1. Field of the Invention
The present invention provides a method and related apparatus for reducing memory accessing while de/compressing multimedia files, and more particularly, a method and related apparatus for reducing memory access by preventing access of null data in the frequency domain.
2. Description of the Prior Art
Since signal detection and processing techniques have been developed and improved upon, media signals, whether static images or motion videos, can be stored, processed, or transmitted by electronic signals with little distortion. However, in general, file sizes of multimedia files, including a variety of media information, are so large that they must be compressed properly for storing and transmitting. Consequently, compressed multimedia files should be decompressed to play. Moreover, because image data of multimedia files are rich in high-dimensional data (including two-dimensional images and/or time-domain changes), de/compression processes place high demand on system resources. Therefore, a key development issue in modern information technology is how to de/compress image data files with high efficiency and low cost.
Please refer to FIG. 1, which is a schematic diagram illustrating a typical image compression process, such as the process under MPEG protocol, or Motion Picture Expert Group. Those skilled in the art will recognize that image compression is seen as a coding process for image data, and decompression contrarily a decoding process. As FIG. 1 illustrates, a motion image data M (such as a movie or an animation) can be seen as a series of static pictures, A1, A2, A3, A4, A5, etc. Displayed different pictures as time changes, the motion image data M can be a movie. Besides, in order to increase compression rate, a process 10 undergoes an inter-coding among pictures initially to analyze each difference among pictures as the image data M is compressed; then, a process 12 takes an intra-coding process in a picture based on the outcome of the process 10.
Those skilled in the art will recognize that the differences among pictures are little when displaying a series image of running actions. For example, in FIG. 1, a movie formed by the pictures A1, A2, A3 displays a motion: an object Oj moves in the same background Bk. With exception of the object Oj position different in varied pictures, the background Bk image does not change a lot. In the process 10, a motion detection is taken to compare pictures. As FIG. 1 illustrates, the motion detection in the picture A1, A2 can roughly conclude that the object Oj moves but the background Bk does not change. Furthermore, a vector V12 is computed to represent moving direction and distance of the object Oj. In other words, the picture A2 can roughly be obtained by moving the object Oj in the picture A1 along with the vector V12, this processes being named dynamic (or action) compensation. A predictive picture of the picture A2 operated by shifting the object Oj in the picture A1 along with the vector V12 can be a prediction P2, not shown in FIG. 1. Indeed, the prediction P2 may not absolutely match the picture A2 (such as reflected light on the object Oj changes a little between the pictures A1 and A2), but their differences should not be significant. Hence, subtracting the prediction P2 from the picture A2 generates a difference picture, named difference D12. That is to say, the picture A2 can be gained by dynamically compensating the picture A1 and adding the difference D12, and this means that all image information of the pictures A1 and A2 can be contained by the picture A1, the vector V12 and the difference D12. In addition, owing to little image information in the difference D12 and slight differences between the prediction P2 and the picture A2, a high level compression is practicable, and the pictures A1, A2 are compressed.
Based on the same method, the picture A3 in FIG. 1 can be obtained from the picture A2, the corresponding vector V23, and the difference D23, so that the movie composed of a series of the pictures A1, A2, A3 can be expressed by the picture A1, the differences D12, D23 and the vectors V12, V23, thus an initial compression to the series motion image is performed. Certainly, the data image M may contain so many irrelative sequences, like pictures A4 and A5, that there might be an entirely different object moving in an entirely different background; therefore, the picture A4 is much different from the picture A3, and the motion detection is cancelled between the pictures A3 and A4, but is executed between the pictures A4 and A5 to take compression for the series image of the pictures A4 and A5 in the process 10.
After compressing/coding the differences among pictures in the process 10, the process 12 compresses/codes the pictures or the differences respectively. For example, in FIG. 1, the pictures A1, A4 and the differences D12, D23, D45 can be further compressed to increase compression rate. Please refer to FIG. 2, which illustrates a compression (or coding) process of in the process 12. To further compress a picture A (like pictures A1, A4, the differences D12, D23, etc.), the picture A is divided into a plurality of small blocks B formed by a plurality of pixels Bij. The frequency domain data matrix C containing a plurality of data elements Cij is obtained by two-dimensional frequency-domain transformations within each block B (such as discrete cosine transformation, or DCT). In other words, each data element Cij represents the quantity (i.e. the frequency domain component or coefficient) of the block B in frequency domain. Combining each Qij, the quantized data element Cij, can construct the frequency domain data matrix Q, or frequency domain matrix. Arranging each data element Qij of the data matrix Q in a specified order to be a series of one-dimensional data matrix S is called a serial scanning. Another one-dimensional data matrix R is gained after a running length coding to the data matrix S. Then, a data matrix H is generated after Huffman coding to the data matrix R. Combining data matrix H corresponding the block B finishes coding the pictures A.
In the process 12, because each block B is just a part of the picture A, values of pixel Bijs in a block B should not be significant, that is, the values of pixels in the same block tend to be similar. After the block B undergoes the frequency-domain transformation/quantization, this represents that high frequency domain quantities of the data element Cij and Qij should almost be null, or be negligible. That is to say, the frequency domain data matrix C and Q are sparse matrices. Therefore, after the one-dimensional matrix S is scanned and arranged from the data matrix Q, data elements Sks (each equals to one data element Qij) of the data matrix S are among many null values. As the data matrix S undergoes the running length coding, numbers of null data elements between two non-null data elements Sks are coded to reduce the length of the data matrix S. For example, when ten null data elements exist between two non-null data elements Si and Sj, it does not store the ten null data elements between Si and Sj, but records the number of ten null data elements by the running length coding to the data element Sj. So, the bit length of the data matrix R generated from the running length coding of the data matrix S can be reduced a lot. After Huffman coding, the bit length of the data matrix R is further compressed, and a data matrix H is generated. Combining each data matrix H generated from the compression of each block B, the compressed picture of the picture A becomes a multimedia file.
Obviously, if the image data is static, it undergoes the process 12 without the process 10, such as a joint Photo-graphic Experts Group, or JPEG, process. Please refer to FIG. 2 (and FIG. 1) again. The decompression process is basically the reverse of the compression process. The data matrix H of a compressed multimedia file is decompressed to the data matrix S, and then is arranged to the two-dimensional data matrix Q (named inverse scanning). Dequantizing the data matrix Q obtains the frequency domain data matrix C. The block B can be obtained by taking an inverse discrete cosine transformation to the data matrix C. Combining varied blocks B obtains the picture A. If the original image data is a motion image data, the original motion image data can be combined by dynamically compensating the picture A, thereby finishing the decompression (or decoding).
Please refer to FIG. 3 illustrating a function block diagram of a prior art processing circuit 20. The processing circuit 20 performs de/compression (or de/coding) for image data, and includes a central processing unit 14, a memory access module 16, a dynamic estimation module 18, a frequency-domain transformation/quantization module 22, an inverse frequency-domain transformation/dequantization module 24, and an inner memory 28 (such as random access memory). The central processing unit 14 controls operations of processing circuit 20. The memory access module 16 can achieve the function of direct memory access, or DMA, so that the processing circuit 20 can access an outer memory 26 (such as loading the image data waiting for compression from the outer memory 26). In the process 10 shown in FIG. 1, the dynamic estimation module 18 can take dynamic estimation. In the process 12 in FIG. 1, the frequency-domain transformation/quantization module 22 can achieve frequency-domain transformation and quantization. Contrarily, the inverse frequency-domain transformation/dequantization module 24 can recover compressed multimedia files from one-dimensional data matrixes to two-dimensional blocks in order to decompress (decode) and generate each picture. To support operations of each module in the processing circuit 20, the processing circuit 20 also includes an inner memory 28 to register data for the operations of each module.
For example, when image data compression (coding) is performed by the prior art processing circuit 20, the frequency-domain transformation/quantization module 22 transforms/quantizes the block B of each picture (please refer to FIG. 2) to the two-dimensional data matrix Q, and each data element Qij of the data matrix Q is written (stored) into the inner memory 28 sequentially. Progressing to serial scanning, each data element of the data matrix Q is read from the inner memory 28 sequentially and forms a one-dimensional data matrix S. Then, the next block B is processed.
In summary, it is necessary to access the inner memory 28 frequently in the prior art processing circuit 20. As FIG. 1 and FIG. 2 show, a data image M may include a lot of pictures A, and a picture A contains a lot of blocks B each corresponding to the frequency domain data matrix Q. When the processing circuit 20 compresses images, each data element Qij of the data matrix Q is stored into the inner memory 28 one by one. Besides, when serial scanning, each data element Qij is read sequentially. Actually, as mentioned above, the frequency domain matrix Q might be a sparse matrix, which means that most data elements Qij are nulls, and this is the reason that the running length coding can reduce the length of the matrix S in that the data matrix R only records the number of null data elements after running length coding, instead of arranging these null data element exactly in the data matrix R. However, when the prior art processing circuit 20 accesses the data matrix Q from the inner memory 28, there is no better way to utilize characters of a sparse matrix, but to access each data element Qij one by one. As a result, the processing circuit 20 needs to access its inner memory 28 frequently in the de/coding process, so that its occupied memory resources cannot be reduced effectively. In achieving the function of high speed de/compression, the processing circuit 20 should use high frequency inner memory (that is, it must access more data in a unit of time), so that the cost of circuit design and manufacture cannot be reduced.